# coding: utf8
# datetime: 2021-04-15
# 题目地址: https://leetcode-cn.com/problems/house-robber/

from typing import List


class Solution:
    def rob(self, nums: List[int]) -> int:
        len_nums = len(nums)
        if len_nums == 0:
            return 0
        elif len_nums == 1:
            return nums[0]
        # resp = [0]*len_nums
        # resp[0] = nums[0]
        # resp[1] = max(nums[0], nums[1])
        first = nums[0]
        second = max(first, nums[1])
        for i in range(2, len_nums):
            tmp = second
            second = max(first+nums[i], second)
            first = tmp
            # resp[i] = max(resp[i-2]+nums[i], resp[i-1])
        # return resp[-1]
        return max(first, second)

a = Solution()
print(a.rob([2,1,1,2]))